<?php
/**
 * 二分查找
 * @param array   $seq A list of integers
 * @param integer $key The integer to be searched for
 * @return bool|mixed Return $key or not found (false)
 */
function binary_search(array $seq, $key)
{
    $loop = 0;
    $low = 0;
    $high = count($seq);

    while ($high >= $low) {
        $middle = (int)(($high + $low) / 2);

        if ($seq[$middle] < $key) {
            $low = $middle + 1;
            $loop++;

        } elseif ($seq[$middle] > $key) {
            $high = $middle - 1;
            $loop++;

        } else {
            return [
                'position' => $middle,
                'loop'     => $loop
            ];
        }
    }

    return false;
}
